package 数字字符串20250224;

import java.util.HashMap;

/**
 * 560.和为k的子数组的数量
 * https://leetcode.cn/problems/subarray-sum-equals-k/description/
 * @author
 * @version 1.0
 * @className SumIsKSub
 * @since 1.0
 */
public class SumIsKSub {
    /**
     * 使用前缀和，将每一个前缀和以及该和出现的次数都存于map中，
     * 循环每一个元素，寻找当前前缀和-目标值，
     * map中是否有存在的前缀和，
     * 存在就加上前缀和出现的次数
     * 注意：判断需要在存map之前，否者k=0会报错
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        int res=0;
        HashMap<Integer, Integer> map = new HashMap<>();
        Integer preSum = 0;
        //自身的值也可以和k相等，也算一次解
        map.put(0,1);
        for(int i=0;i<nums.length;i++){
            preSum+=nums[i];
            if(map.containsKey(preSum-k)){
                res+=map.get(preSum-k);
            }
            if(map.containsKey(preSum))
                map.put(preSum,map.get(preSum)+1);
            else
                map.put(preSum,1);
        }
        return res;
    }
}
